# 动态规划的本质是复用之前的结果


class Solution:

    def numSquares(self, n):
        # 创建一个复用数组
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            # 先找出开方以后是整数的数
            if i ** 0.5 % 1 == 0:
                dp[i] = 1
            else:
                # 不为整数时，至少有一个
                dp[i] = 1 + min([dp[i - j*j] for j in range(1, int(i**0.5)+1)])


        return dp[-1]


if __name__ == '__main__':

    n = 12
    sol = Solution()
    res = sol.numSquares(n)
    print(res)